「NOIP 2023」三值逻辑

这道题其实挺简单的，但是某人能把并查集的$get$函数写成$fa[x]==get(fa[x])$直接$100->20$

读懂题意后，本蒟蒻想到了三个方向去完成本题(且根据洛谷上的题解这三个方法均正确)，但是我只写了一种，所以先简单介绍一下前两种方法

---

1.从这个二元限制来讲，大多数人应该一眼顶针会想到2-SAT，而再仔细观察一下这个限制方式，其实就是2-SAT中的连一条边

于是跑tarjan求SCC，再统计答案就可以了

2.一边连向另一边+不能同时满足(连不等关系)，二分图秒了，但是这个方法本蒟蒻没有经过深层次的思考，具体见luogu第二篇题解

---

3.关系限制，相同关系分在同一组，应该可以很快的想出并查集的处理方式

于是我们进行相同值分组并记录每个联通块的大小，因为是原值与取反两种关系，所以可以想到扩展域并查集

如何判断是否未知呢，很简单，它和他的反在同一集合内就是了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair< int,int >
#define QWQ return 0;

const int N=1e5+10;

int fa[N], siz[N], flag[N];

int get( int x ){ return ( fa[x] == x ? x : fa[x] = get( fa[x] ) ); }

void merge( int x,int y )
{ 
	x=get( x ), y=get( y );
	if( x != y ) siz[x]+=siz[y], fa[y]=x;
}

int no( int x )
{
	if( x == -1 ) return -2;
	if( x == -2 ) return -1;
	if( x == -3 ) return -3;
	return x^1;
}

bool check( int x,int rt,int fg )
{
	if( ( flag[x]>>1 ) == rt ) return fg^( flag[x]&1 );
	return check( flag[x]>>1,rt,fg^( flag[x]&1 ) );
}

void sovel()
{
	int n, m;
	cin>>n>>m;
	for( int i=1;i<=n;i++ ) fa[i]=i, siz[i]=1, flag[i]=( i<<1  );
	for( int i=1, x, y;i<=m;i++ )
	{
		char op;
		cin>>op>>x;
	    	 if( op == 'T' ) flag[x]=-1;
		else if( op == 'F' ) flag[x]=-2;
		else if( op == 'U' ) flag[x]=-3;
		else if( op == '+' ) cin>>y, flag[x]=flag[y];
		else if( op == '-' ) cin>>y, flag[x]=no( flag[y] );
	}
	for( int i=1;i<=n;i++ ) 
		if( flag[i] > 0 ) merge( flag[i]>>1,i );
	int res=0;
	for( int i=1;i<=n;i++ )
		if( i == get( i ) && ( flag[i] == -3 || ( flag[i] > 0 && check( i,i,0 ) ) ) )
			res+=siz[i];
	cout<<res<<"\n"; 
}

int main()
{
	freopen( "tribool.in","r",stdin );
	freopen( "tribool.out","w",stdout );
	ios::sync_with_stdio( false );
	cin.tie( nullptr ), cout.tie( nullptr );
	int c, t;
	for( cin>>c>>t;t;t-- ) sovel();
	QWQ
}